package dataStructures;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class DataStructTest {
    public static void main(String[] args) {
        NumIslandsSolution n = new NumIslandsSolution();
        int res = n.numIslands(new char[][]{{'0','1'},{'1', '0'}});
        System.out.println(res);
    }
}

/**
 * 全量并查集， 最长连续序列
 */
class DataStructTestUnionSet{

    private class UnionSetNode<T>{
        T val;
        UnionSetNode(T val){ this.val = val; }
    }

    private class UnionSet<T>{

        // 对应节点
        private Map<T, UnionSetNode<T>> valMap = new HashMap<>();
        // 父节点
        private Map<UnionSetNode<T>, UnionSetNode<T>> fatherMap = new HashMap<>();
        // 每个集合数量
        private Map<UnionSetNode<T>, Integer> counts = new HashMap<>();
        // 全局max
        private Integer max = 0;
        
        UnionSet(List<T> values){
            for(T val : values){
                UnionSetNode<T> node = new UnionSetNode<>(val);
                valMap.put(val, node);
                fatherMap.put(node, node);
                counts.put(node, 1);
            }
            if(values != null) max = 1;
        }

        private UnionSetNode<T> findFather(UnionSetNode<T> cur){
            Stack<UnionSetNode<T>> path = new Stack<>();
            while(cur != fatherMap.get(cur)){
                path.push(cur);
                cur = fatherMap.get(cur);
            }
            while(!path.empty()){
                fatherMap.put(path.pop(), cur);
            }
            return cur;
        }

        void union(T x, T y){
            // 父节点相同
            if(!valMap.containsKey(x) || !valMap.containsKey(y)){
                return;
            }
            // 父节点不同则合并
            UnionSetNode<T> xHead = findFather(valMap.get(x));
            UnionSetNode<T> yHead = findFather(valMap.get(y));
            if(xHead != yHead){
                int xSetSize = counts.get(xHead);
                int ySetSize = counts.get(yHead);
                UnionSetNode<T> bigHead = xSetSize > ySetSize ? xHead : yHead;
                UnionSetNode<T> smallHead = bigHead == xHead ? yHead : xHead;
                fatherMap.put(smallHead, bigHead);
                counts.put(bigHead, xSetSize + ySetSize);
                max = Math.max(max, xSetSize + ySetSize);
                counts.remove(smallHead);
            }
        }

        int getMax(){
            return this.max;
        }

        boolean isSameSet(T x, T y){
            if(!valMap.containsKey(x) || !valMap.containsKey(y)){
                return false;
            }
            return findFather(valMap.get(x)) == findFather(valMap.get(y));
        }

    }

    /**
     * 128. 最长连续序列
     * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
        请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
        
        示例 1：
        输入：nums = [100,4,200,1,3,2]
        输出：4
        解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
        
        示例 2：
        输入：nums = [0,3,7,2,5,8,4,6,0,1]
        输出：9
        
        示例 3：
        输入：nums = [1,0,1,2]
        输出：3
     */
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        Set<Integer> s = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            s.add(nums[i]);
            list.add(nums[i]);
            }
        UnionSet<Integer> unionSet = new UnionSet<>(list);
        Iterator<Integer> it = s.iterator();
        while(it.hasNext()){
            Integer num = it.next();
            if(s.contains(num + 1)){
                unionSet.union(num + 1, num);
            } else if(s.contains(num - 1)){
                unionSet.union(num - 1, num);
            }
        }
        return unionSet.max;

    }

    


    /**
     * 200. 岛屿数量 DFS，并查集
     */

     /**
      * 130. 被围绕的区域
      */

      /**
       * 547. 省份数量
       */

       /**
        * 684. 冗余连接 环检测
        */





}

/**
 * 全量并查集-情侣牵手
 */
class MinSwapsCouplesSolution1{


    /**
     * 765. 情侣牵手 思维题 贪心+并查集
     * 
     * n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。

        人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。

        返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。

        示例 1:
        输入: row = [0,2,1,3]
        输出: 1
        解释: 只需要交换row[1]和row[2]的位置即可。

        示例 2:
        输入: row = [3,2,0,1]
        输出: 0
        解释: 无需交换座位，所有的情侣都已经可以手牵手了。
     */
    
    public int minSwapsCouples(int[] row) {
        // 图论转换
        // 将每对情侣的位置看做是图中的一个节点
        // 如果两个节点有值需要交换，那么这两个节点就连接起来
        // 最后每个连通图（也就是环）的 边-1 的和就是答案
        
        // 每两个点为一个组，记录某个人所在的组
        Map<Integer, Integer> group = new HashMap<>();
        Set<Integer> groupSet = new HashSet<>();
        for(int i = 0; i < row.length; i++){
            group.put(row[i], i / 2);
            groupSet.add(i / 2);
        }
        UnionSet unionSet = new UnionSet(groupSet);
        for(int i = 0; i < row.length; i++){
            // 如果在每组的第一个位置, 并且该组已经分配好了,直接跳到下一组
            if(i % 2 == 0 && (row[i] / 2 == row[i + 1] / 2)){
                i++;
            } else {
                int thisGroup = group.get(row[i]);
                // 找到当前数的另一半，如果这两个组不在同一个集合，则合并
                int other = row[i] % 2 == 0 ? row[i] + 1 : row[i] - 1;
                int otherGroup = group.get(other);
                if(!unionSet.isSameSet(thisGroup, otherGroup)){
                    unionSet.union(thisGroup, otherGroup);
                }
            }
        }
        int ans = unionSet.getAns();
        return ans;
    }

    /**
     * 对情侣问题定制的并查集
     */
    private class UnionSetNode{
        UnionSetNode next;
        UnionSetNode(){ this.next = null;}
    }

    private class UnionSet{
        // 值对应的集合
        private Map<Integer, UnionSetNode> nodes = new HashMap<>();
        // 集合的大小
        private Map<UnionSetNode, Integer> size = new HashMap<>();
        // 合并的此处
        private Integer ans;
        
        UnionSet(Set<Integer> set){
            Iterator<Integer> it = set.iterator();
            while(it.hasNext()){
                Integer group = it.next();
                UnionSetNode node = new UnionSetNode();
                node.next = node;
                nodes.put(group, node);
                size.put(node, 1);
            }
            ans = 0;
        }

        private UnionSetNode findFather(int val){
            UnionSetNode node = nodes.get(val);
            Stack<UnionSetNode> s = new Stack<>();
            while(node.next != node){
                node = node.next;
                s.push(node);
            }
            while(!s.empty()){
                s.pop().next = node;
            }
            return node;
        }

        void union(int a, int b){
            if(!nodes.containsKey(a) || !nodes.containsKey(b)){
                return ;
            }
            UnionSetNode aHead = findFather(a), bHead = findFather(b);
            if(aHead != bHead){
                int aSize = size.get(aHead), bSize = size.get(bHead);
                UnionSetNode bigHead = aSize > bSize ? aHead : bHead;
                UnionSetNode smallHead = bigHead == aHead ? bHead : aHead;
                smallHead.next = bigHead;
                size.put(bigHead, aSize + bSize);
                size.remove(smallHead);
                ans += 1;
            }
        }

        boolean isSameSet(int a, int b){            
            if(!nodes.containsKey(a) || !nodes.containsKey(b)){
                return false;
            }
            if(findFather(a) == findFather(b))
                return true;
            return false;
        }

        Integer getAns(){
            return this.ans;
        }
    }



}

/**
 * 简化并查集-情侣牵手
 */
class MinSwapsCouplesSolution{
    public int minSwapsCouples(int[] row){
        // 初始化有多少对情侣
        int n = row.length / 2;
        UnionFind unionFind = new UnionFind(n);

        // 将两个作为看做是一个节点
        // 交换次数为 sum(每个连通分量的边数)
        for(int i = 0; i < row.length; i += 2){
            int a = row[i] / 2;
            int b = row[i + 1] / 2;
            unionFind.union(a, b);
        }
        return unionFind.merge;
    }

    /**
     * 数组优化简化并查集结构
     * 在大多数算法题中，节点是 0 到 n-1 的整数，完全没必要用对象封装。
     */
    class UnionFind{

        /**
         *  1.在按秩合并（Union by Rank）中，rank 的作用是：
                    避免将深树挂到浅树上，防止树变得太深。
            2.它并不是为了“精确记录高度”，而是作为一个保守估计。
            3.即使路径压缩后树变扁了，rank 依然保留原来的值，但它仍然是一个安全的上界。
         */

        int[] parent; // parent[i] 表示第 i 个节点的父节点
        int[] rank; // rank[i] 表示以 i 为根的树的“秩”（树的近似高度），用户合并时判断大小，小挂大
        int merge; // 答案

        UnionFind(int n){
            parent = new int[n];
            rank = new int[n];
            merge = 0;
            for(int i = 0; i < n; i++) parent[i] = i;
        }

        int findFather(int val){
            if(parent[val] != val){
                parent[val] = findFather(parent[val]);
            }
            return parent[val];
        }

        void union(int a, int b){
            // 把矮的树挂到高的树上 → 整体高度不变 ✅
            // 只有当两棵树一样高时，合并后高度才会 +1 → rank 才需要 +1
            int aHead = findFather(a), bHead = findFather(b);
            if(aHead != bHead){
                if(rank[aHead] > rank[bHead]){
                    parent[bHead] = aHead;
                } else if(rank[aHead] < rank[bHead]){
                    parent[aHead] = bHead;
                } else { // 相等时随便挂，并且更新rank
                    parent[aHead] = bHead;
                    rank[bHead]++;
                }
                merge++;
            }
        }
    }
}


/**
 * 200. 岛屿数量 DFS，并查集
 */
class NumIslandsSolution{

    private int m;
    private int n;
    private char[][] grid;

    public int numIslands(char[][] grid) {
        m = grid.length; n = grid[0].length; this.grid = grid;

        UnionFind uf = new UnionFind(m * n);
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] != '1')
                    continue;
                if(inGrid(i + 1, j))
                    uf.union(n * i + j, n * (i + 1) + j);
                if(inGrid(i - 1, j))
                    uf.union(n * i + j, n * (i - 1) + j);
                if(inGrid(i, j + 1))
                    uf.union(n * i + j, n * i + (j + 1));
                if(inGrid(i, j - 1))
                    uf.union(n * i + j, n * i + (j - 1));
            }
        }
        Set<Integer> indexs = new HashSet<>();
        for(int val = 0; val < m * n; val++){
            int index = uf.find(val);
            int i = index / n;
            int j = index % n;
            if(grid[i][j] == '1'){
                indexs.add(index);
            }
        }
        return indexs.size();
    }
    // 判断越界否？
    private boolean inGrid(int i, int j){
        boolean in = i >= 0 && i < m && j >= 0 && j < n;
        if(in && this.grid[i][j] == '1')
            return true;
        return false;
    }

    class UnionFind{
        int[] parent;
        int[] rank;
        UnionFind(int n){
            parent = new int[n];
            rank = new int[n];
            for(int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int i){
            if(i != parent[i])
                parent[i] = find(parent[i]);
            return parent[i];
        }
        void union(int a, int b){
            int aHead = find(a), bHead = find(b);
            if(aHead != bHead){
                if(rank[aHead] < rank[bHead]){
                    parent[aHead] = bHead;
                } else if(rank[aHead] > rank[bHead]){
                    parent[bHead] = aHead;
                } else {
                    parent[aHead] = bHead;
                    rank[bHead]++;
                }
            }
        }
    }

}


/**
 * 并查集-迪杰特斯拉-图的最小生成树
 */



